#pragma once
/** MTBLib::AllocList by Medi H.B.T.
 * This is a header-only library. */

#include <cstdint>
#include <deque>

namespace MTBLib {
    /** @class MTBLib.AllocList
     * 动态增长的ID分配表，本质上是共用内存空间的两个链表.
     * 使用std::deque存放结点.
     * 注意: 最小的ID是2. */
    class AllocList {
    public:
        /** ErrorType */
        enum ErrorType {
            NO_ERR = 0x0,
            BASE          = 0x8001'0000,
            OVERFLOW      = 0x8001'0001,
            EMPTY         = 0x8001'0002,
            NOT_ALLOCATED = 0x8001'0003,
        };
        /** Item */
        struct Item {
            int  prev, next;
            bool allocated;
        };
    public:
        std::deque<Item> id_buff;
    public:
        AllocList(): id_buff() {
            id_buff.push_back({-1, -1, false});
            id_buff.push_back({-1, -1, true});
        }

        bool is_empty() const { return (id_buff.size() == 2); }
        bool is_allocated(int id) const
        {
            return (id >= 0) && (id <= id_buff.size()) &&
                id_buff[id].allocated;
        }


        /**
         * @fn alloc()
         * @brief 分配一个新的ID
         * 在给定的AllocList对象中分配一个新的ID，并将其添加到已分配的元素链表中。
         * @return 返回分配的ID */
        int alloc()
        {
            if (id_buff[0].next == -1) {
                id_buff.push_back({0, -1, false});
                id_buff[0].next = id_buff.size() - 1;
            }
            /* remove the first "unused" id */
            int ret = id_buff[0].next;
            int ret_next = id_buff[ret].next;
            id_buff[0].next = ret_next;
            if (ret_next != -1)
                id_buff[ret_next].prev = 0;

            /* and let it join in the "used" list. */
            ret_next = id_buff[1].next;
            id_buff[ret] = {1, ret_next, true};
            if (ret_next != -1)
                id_buff[ret_next].prev = ret;
            id_buff[1].next = ret;

            return ret;
        }

        /** @fn free(int id)
         * @brief 释放已分配的ID, 并将该ID分配到未分配的链表中。
         * @throw MTBLib::AllocList::ErrorType 错误状态。见ErrorType枚举。 */
        void free(int id)
        {
            if (!is_allocated(id))
                throw ErrorType::NOT_ALLOCATED;
            /* remove the target id */
            int id_prev = id_buff[id].prev;
            int id_next = id_buff[id].next;
            id_buff[id_prev].next = id_next;
            if (id_next != -1)
                id_buff[id_next].prev = id_prev;

            /* and let it join in the "unused" list. */
            id_next = id_buff[0].next;
            id_buff[id] = {0, id_next, false};
            if (id_next != -1)
                id_buff[id_next].prev = id;
            id_buff[0].next = id;
        }
    };
};
